package solution1.demo.demo2;


import java.util.*;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

public class Solution {

    //1.平衡二叉树(dfs)
//    public boolean isBalanced(TreeNode root) {
//        //去求每一个子树的左右高度差
//        if(root == null) {
//            return true;
//        }
//        if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
//            return false;
//        }
//        return isBalanced(root.left) && isBalanced(root.right);
//    }
//
//    private int maxDepth(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
//    }

    //2.平衡二叉树(优化)
    public boolean isBalanced(TreeNode root) {
        //去求每一个子树的左右高度差
        if(root == null) {
            return true;
        }
        return maxDepth(root) > 0;
    }

    private int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        if(left >= 0 && right >= 0 && Math.abs(left - right) <= 1) {
            return Math.max(left, right) + 1;
        }
        return -1;
    }

    //3.叉树的所有路径(StringBuilder)
    private List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null) {
            return res;
        }
        StringBuilder path = new StringBuilder();
        dfs(root, path);
        return res;
    }

    private void dfs(TreeNode root, StringBuilder path) {
        if(root == null) {
            return;
        }
        int numSize = String.valueOf(root.val).length();
        if(root.left == null && root.right == null) {
            path.append(root.val);
            res.add(path.toString());
            path.delete(path.length() - numSize ,path.length());
            return;
        }
        path.append(root.val);
        path.append("->");
        dfs(root.left, path);
        dfs(root.right, path);
        path.delete(path.length() - numSize - 2 ,path.length());
    }

    //4.左叶子结点之和(dfs)
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return root.val;
        }
        int left = sumOfLeftLeaves(root.left);
        int right = sumOfLeftLeaves(root.right);
        return left + right;
    }

    //5.找树左下角的值(dfs)
    public void dfs(TreeNode root, int depth) {
        if(root == null) {
            return;
        }
        if(prevDepth < depth) {
            flag = true;
        }
        if(prevDepth < depth && flag) {
            value = root.val;
            flag = false;
            prevDepth = depth;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }

    //6.路径总和(dfs)
    private int prevDepth;//记录上次的最大深度
    private int value;//要返回的值
    private boolean flag;//prevDepth < depth
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 1);
        return value;
    }

//    private void dfs(TreeNode root, int targetSum) {
//        if(flag) {
//            return;
//        }
//        if(root == null) {
//            return;
//        }
//        sum += root.val;
//        if(root.left == null && root.right == null) {
//            if(sum == targetSum) {
//                flag = true;
//            }
//        }
//        dfs(root.left, targetSum);
//        dfs(root.right, targetSum);
//        sum -= root.val;
//    }
//
//    private int sum;
//    private boolean flag;
//    public boolean hasPathSum(TreeNode root, int targetSum) {
//        if(root == null) {
//            return false;
//        }
//        dfs(root, targetSum);
//        return flag;
//    }

//    //7.从中序与后序遍历序列构造二叉树(分治)
//    //后序遍历中指向根节点的指针
//    private int cur;
//    private TreeNode createTreeNode(int[] inorder, int[] postorder, int start, int end) {
//        if(start > end) {
//            return null;
//        }
//        TreeNode root = new TreeNode(postorder[cur]);
//        //找到 中序遍历所在下标，进行分治
//        int index = fundIndex(inorder, postorder[cur], start, end);
//        cur--; //寻找下一个根节点
//        //后序遍历反过来因该是 中右左 ，因此先得到的是右树的结点，那么就需要先建立右树
//        root.right = createTreeNode(inorder, postorder, index + 1, end);
//        root.left = createTreeNode(inorder, postorder, start, index - 1);
//        return root;
//    }
//
//    private int fundIndex(int[] inorder, int key, int start, int end) {
//        for(int i = start; i <= end; i++) {
//            if(inorder[i] == key) {
//                return i;
//            }
//        }
//        return -1;
//    }
//
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        this.cur = postorder.length - 1;
//        return createTreeNode(inorder, postorder, 0, inorder.length - 1);
//    }

//    //8.从前序与中序遍历序列构造二叉树(分治)
//    private int cur;
//    private TreeNode createTree(int[] preorder, int[] inorder, int start, int end) {
//        if(start > end) {
//            return null;
//        }
//        TreeNode root = new TreeNode(preorder[cur]);
//        //寻找这个值在中序遍历的哪一个下标位置出现
//        int index = fundIndex(inorder, preorder[cur], start, end);
//        //分别去建左右子树(因为先序遍历是中左右，那么拿到中间节点后，下一个拿到的因该是 左节点,因此先建立左树)
//        cur++;
//        root.left = createTree(preorder, inorder, start, index - 1);
//        root.right = createTree(preorder, inorder, index + 1, end);
//        return root;
//    }
//
//    private int fundIndex(int[] inorder, int key, int start, int end) {
//        for(int i = start; i <= end; i++) {
//            if(inorder[i] == key) {
//                return i;
//            }
//        }
//        return -1;
//    }
//
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        return createTree(preorder, inorder, 0, preorder.length - 1);
//    }

    //9.最大二叉树(dfs)
    private TreeNode createTree(int[] nums, int left, int right) {
        if(left > right) {
            return null;
        }
        //寻找最大值下标
        int maxIndex = fundMaxValue(nums, left, right);
        //建树
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = createTree(nums, left, maxIndex - 1);
        root.right = createTree(nums, maxIndex + 1, right);
        return root;
    }

    private int fundMaxValue(int[] nums, int left, int right) {
        int max = nums[left];
        int index = left;
        for(int i = left + 1; i <= right; i++) {
            if(nums[i] > max) {
                max = nums[i];
                index = i;
            }
        }
        return index;
    }

    private int cur;
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return createTree(nums, 0, nums.length - 1);
    }

    //10.合并二叉树(dfs)
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) {
            return null;
        }
        if(root1 != null && root2 == null) {
            return root1;
        }
        if(root2 != null && root1 == null) {
            return root2;
        }
        //这里是不为空
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }

}

class Main {
    public static void main(String[] args) {

        TreeNode t3 = new TreeNode(3);
        TreeNode t9 = new TreeNode(9);
        TreeNode t20 = new TreeNode(20);
        TreeNode t15 = new TreeNode(15);
        TreeNode t7 = new TreeNode(7);

        t3.left = t9;
        t3.right = t20;
        t20.left = t15;
        t20.right = t7;

        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        Solution solution = new Solution();



    }
}